



		PARITATE - SOLUTIE
	       ---------------------

(data de Dumitru Bogdan)

	Aceasta problema a fost considerata de majoritatea concurentilor drept
cea mai "inteligenta: problema dintre cele propuse spre rezolvare in prima zi
de concurs.
	Dupa lectura textului se contureaza o prima idee de rezolvare: trebuie
sa concatenam intervalele date pentru care limita superioara a unuia si limi-
ta inferioara a celuilalt sunt numere consecutive, in inercarea de a obtine o
contradictie (un interval despre care sa stim ca include atat un numar par, cat
si un numar impar de numere 1 - lucru evident imposibil).
	Aceasta idee prezinta un dezavantaj imens: ea creeaza noi si noi inter-
vale, existand multe situatii pentru care memoria pusa de obicei la dispozitie
(cateva sute de KB) nu este deloc suficienta.
	Remarcam ca in loc de a concatena intervale, obtinand intervale noi,tot
mai mari, ar fi mult mai bine daca am "scadea" intervale,obtinand intervale mai
mici, cu care se lucreaza mai usor. Vom spune, pentru simplificarea exprimarii,
ca un interval "este par", respectiv "este impar")', daca el contine un numar par,
respectiv impar, de cifre de 1. Principiul de baza al rezolvarii va fi: avand pa-
ritatile intervalelor [X,Y] si [X,Z], cu Y<Z, retinem paritatile intervalelor
[X,Y] si [Y+1,Z] (adica a intervalului de lungime minima si a "diferentei" intre
cele doua intervale). EVident, orice prelucrare de intervale nu se poate baza de-
cat pe coincidente ale limitelor intervalelor (in afara acestora neputand aparea
nici o contradictie).
	Mai ramane de vazut cum "reducem" intr-o maniera eficienta intervalele.
	Solutia cea mai buna pare a fi urmatoarea: retinem un vector A in care
fiecare element reprezinta un interval (dat prin limite si paritate). Vectorul este
permanent sortat dupa limita de inceput a intervalelor. La citirea unui nou inter-
val, acesta este adaugat la sfarsitul vectorului.
	Gasim apoi (daca exista) un interval care sa inceapa in acelasi punct cu
intervalul citit. Notand cu I acest interval si cu J noul interval, deosebim 3 ca-
zuri:

1) limita superioara a intervalului I este mai mare decat limita superioara a inter-
valului J; in acest caz se inverseaza intervalele, urmand ca algoritmul sa trateze
cazul 3);
2) limita superioara a intervalului I este egala cu limita superioara a intervalului J;
apar aici doua subcazuri:
2.1) daca cele 2 intervale au aceeasi paritate, noua informatie este redundanta si
este eliminata
2.2) in caz contrar, am detectat o contradictie; se afiseaza numarul de raspunsuri
citie si se suspenda executia programului;
3) limta superioara a intervalului I este mai mica decat limita superioara a inter-
valului J; atunci intervalul J este inlocuit cu un nou interval, cu proprietatile:
- limita inferioara este egala cu limita superioara a intervalului I, la care se
adauga 1;
- limita superioara este egala cu limita superioara a intervalului J;
- intervalul este par daca intervalele I si J aveau aceeasi paritate si impar, in
caz contrar;
	Se continua in acelasi mod baleierea vectorului de intervale, reducand
acolo unde este posibil.
	Daca se termina citirea, inseamna ca nu a fost detectata nici o contradictie.
Se afiseaza deci numarul raspunsurilor citite si se termina executia.

	Complexitatea maxima a acestui algoritm este O(N^2). Insa, pe un anumit test,
este foarte putin probabil ca baleierea vectorului sa se faca integral de fiecare
data (un astfel de caz ar fi acela in care intervalele sunt date in ordinea descres-
catoare a limitelor inferioare).